function getNext(str) {
    let j = 0;
    let next = []
    next[0] = j
    for (let i = 1; i < str.length; i++) {
        while (j >= 0 && str[i] !== str[j]) {
            j = next[j - 1]
        }
        if (str[i] === str[j]) {
            j++
        }
        next[i] = j
    }
    return next
}
